package com.cjm.algorithm;

import java.util.Arrays;

public class MuchNums {
    public static void main(String[] args) {

    }

    public static int majorElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return subArrayMajor(nums, 0, nums.length - 1);
    }

    private static int subArrayMajor(int[] nums, int left, int right) {
        int len = right - left + 1;
        if (len <= 5) {
            Arrays.sort(nums, left, right + 1);
            return nums[len / 2 + left];
        }
        int mid = len / 2 + left;
        int leftMajor = subArrayMajor(nums, left, mid);
        int rightMajor = subArrayMajor(nums, mid + 1, right);
        if (isMajor(nums, left, mid, leftMajor)) {
            return leftMajor;
        } else {
            return rightMajor;
        }
    }

    private static boolean isMajor(int[] nums, int left, int right, int key) {
        int cnt = 0;
        int halflen = (right - left + 1) / 2;
        for (int i = 0; i <= right; i++) {
            if (nums[i] == key) {
                cnt++;
                if (cnt > halflen) {
                    return true;
                }
            }
        }
        return false;
    }
}
